import java.util.HashMap;

public class SubarraysDivByK {

    public static void main(String[] args) {
        int[] nums = {4,5,0,-2,-3,1};
        SubarraysDivByK subarraysDivByK = new SubarraysDivByK();
        System.out.println(subarraysDivByK.subarraysDivByK(nums, 5));
    }

    public int subarraysDivByK1(int[] nums, int k) {
        int sum = 0;
        HashMap<Integer, Integer> maps = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            maps.put((sum % k + k) % k, maps.getOrDefault((sum % k + k) % k, 0) + 1);
            sum += nums[i];
            ans += maps.getOrDefault((sum % k + k) % k, 0);
        }
        return ans;
    }

    public int subarraysDivByK(int[] nums, int k) {
        int sum = 0;
        HashMap<Integer, Integer> maps = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            maps.put(Math.floorMod(sum, k), maps.getOrDefault(Math.floorMod(sum, k), 0) + 1);
            sum += nums[i];
            ans += maps.getOrDefault(Math.floorMod(sum, k), 0);
        }
        return ans;
    }
}
